The X-Philes (2nd Revision)/The X-Philes Number 1 (1995).iso/xphiles/hp48_2/star-1_0.tar/ctt.c

C/C++ Source or Header | 1991-03-22 | 5KB | 225 lines

/* ctt.c -- Character Transition Tree Operations

This file is part of STAR, the Saturn Macro Assembler.

   STAR is not distributed by the Free Software Foundation. Do not ask
them for a copy or how to obtain new releases. Instead, send e-mail to
the address below. STAR is merely covered by the GNU General Public
License.

Please send your comments, ideas, and bug reports to
Jan Brittenson <[e-mail]>

*/


/* Copyright (C) 1991 Jan Brittenson.

   STAR is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 1, or (at your option) any
later version.

   STAR is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.

   You should have received a copy of the GNU General Public License
along with STAR; see the file COPYING. If not, to obtain a copy, write
to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139,
USA, or send e-mail to [e-mail]. */


#include <stdio.h>
#include "star.h"
#include "symbols.h"
#include "ctt.h"


/* Allocate ctt root */
static CTT_ROOT *ctt_alloc()
{
  CTT_ROOT *ctt_tmp;
  extern char *malloc();


  if(!(ctt_tmp = (CTT_ROOT *) malloc(sizeof(CTT_ROOT))))
    fatal("Cannot allocate CTT root, %d bytes", sizeof(CTT_ROOT));

  bclear((char *) ctt_tmp, sizeof(CTT_ROOT));

  return(ctt_tmp);
}


/* Allocate ctt node */
static CTT_NODE *ctt_node_alloc()
{
  CTT_NODE *ctt_tmp;
  extern char *malloc();


  if(!(ctt_tmp = (CTT_NODE *) malloc(sizeof(CTT_NODE))))
    fatal("Cannot allocate CTT node, %d bytes", sizeof(CTT_NODE));

  bclear((char *) ctt_tmp, sizeof(CTT_NODE));

  return(ctt_tmp);
}


/* Create new ctt root */
CTT_ROOT *ctt_new()
{
  return(ctt_alloc());
}


/* Walk characters */
struct sstruct *ctt_find(ctt_root, cpp)
  CTT_ROOT *ctt_root;
  char **cpp;
{
  CTT_NODE *node, *last_match;
  char *str = *cpp, *save = *cpp, *last_match_str;


  if(!ctt_root || !cpp)
    return((struct sstruct *) 0);

  /* Walk */
  for(last_match = NULL, last_match_str = str,
      node = ctt_root->ctt_node[toupper(*str)];
      node; )
    {
      /* Does the current character match the current node? */
      if(node->ctt_c == toupper(*str))
    {
      /* Yes, do we have a binding here? */
      if(node->ctt_binding)

        /* Yes, then remember this node */
        last_match = node;

      /* Follow match link and move to next char */
      last_match_str = str++;
      node = node->ctt_match;
    }
      else
    /* No, follow fail link */
    node = node->ctt_next;
    }


  /* Return last match point */
  if(last_match)
    {
      /* Make sure we're not stuck with the initial
       * part of a symbol name, such as "sin" in "sing".
       * The latter should be interpreted as sing, rather
       * sin(g). The exception is when the operator name isn't
       * a valid symbol name, e.g. "0x40".
       */
      if(issym(*last_match_str) && issym(last_match_str[1]) &&
     isisym(*save))

    return((struct sstruct *) 0);

      *cpp = last_match_str+1;
      return(last_match->ctt_binding);
    }
  else
    {
      *cpp = save;
      return((SYM_NODE *) 0);
    }
}


/* Convert string to virgin match list */
static CTT_NODE *ctt_make_match(str, binding)
  char *str;
  SYM_NODE *binding;
{
  CTT_NODE *start_node, *node, *new_node;

  start_node = ctt_node_alloc();

  for(node = start_node, start_node->ctt_c = *str++; *str; node = new_node)
    {
      new_node = ctt_node_alloc();

      new_node->ctt_c = *str++;
      node->ctt_match = new_node;
    }

  node->ctt_binding = binding;

  return(start_node);
}


/* Add string to tree */
void ctt_add(ctt_root, str, binding)
  CTT_ROOT *ctt_root;
  char *str;
  SYM_NODE *binding;
{
  CTT_NODE *node;

  if(!ctt_root)
    return;


  /* Walk until we're at the link point */
  if(!(node = ctt_root->ctt_node[*str]))
    {
      /* Virgin tree, initialize */
      ctt_root->ctt_node[*str] = ctt_make_match(str, binding);
      return;
    }

  /* If we drop out of the loop, the string cannot be added */
  while(*str)
    {
      /* Does the current character match the current node? */
      if(node->ctt_c == *str)
    {
      /* Yes, do we have a match link? */
      if(!node->ctt_match)
        {
          /* No - link up here */
          if(*++str)
        node->ctt_match = ctt_make_match(str, binding);
          else
        node->ctt_binding = binding;

          return;
        }

      /* Yes, follow it and move to next char.
       * See if end of string */
      if(!*++str)
        {
          /* This means we're entering a substring, so we
           * just rebind the node.
           */
          node->ctt_binding = binding;
          return;
        }
      node = node->ctt_match;
    }
      else
    /* No, follow fail link */
    if(node->ctt_next)
      node = node->ctt_next;
    else
      {
        /* No fail link - link up here */
        node->ctt_next = ctt_make_match(str, binding);
        return;
      }
    }
}